//
// Created by zhulingfeng on 2020/3/6.
//

#ifndef DATA_STRUCTURE_AND_ALGORITHM_SRC_SEARCH_BINARY_SEARCH_HPP_
#define DATA_STRUCTURE_AND_ALGORITHM_SRC_SEARCH_BINARY_SEARCH_HPP_

#include <vector>
/**
 * @brief Binary search.
 * @return index of target, -1 for not found.
 */
int BinarySearch(const std::vector<int>& vector, int target);
/**
 * @brief Binary search in range [lo, hi].
 * @return index of target, -1 for not found.
 */
int BinarySearch(const std::vector<int>& vector, int target, int lo, int hi);
/**
 * @brief Search first and last index wih value equal to target
 * @return {first_index, last_index} vector, {-1, -1} for not found.
 */
std::vector<int> SearchRange(const std::vector<int>& array, int target);
/**
 * @brief Another implement of SearchRange, not recommended since it's needs
 * to write code with more carefully to avoid bugs.
 */
std::vector<int> SearchRangeWithTricks(const std::vector<int>& array,
                                       int target);
/**
 * @brief Search in rotated array. Assume no duplicates.
 * @return index of target, -1 for not found.
 */
int SearchRotatedArrayWithoutDuplicates(std::vector<int>& array, int target);
/**
 * @brief Another version, seems to have bugs.
 */
int SearchRotatedArrayWithoutDuplicates2(const std::vector<int>& array,
                                         int target);
/**
 * @brief Search in rotated array.
 * @return index of target, -1 for not found.
 */
int SearchRotatedArray(std::vector<int>& array, int target);
#endif  // DATA_STRUCTURE_AND_ALGORITHM_SRC_SEARCH_BINARY_SEARCH_HPP_
